package alogrithm;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/19 11:19
 */
public class GetNumberOfK {
    public int GetNumberOfK(int[] array, int k) {
        int l = binarySearch(array, true, k);
        int r = binarySearch(array, false, k) - 1;
        if (l <= r && r < array.length && array[l] == k && array[r] == k) {
            return r - l + 1;
        }
        return 0;
    }

    // b表示是寻找最左的tar还是找最右的tar,true表示左, false表示右
    private int binarySearch(int[] array, boolean b, int tar) {
        int ans = 0;
        int l = 0, r = array.length - 1;
        while (l <= r) {
            int mid = (r + l) / 2;
            if (array[mid] > tar || (b && array[mid] >= tar)) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
}
